// FixedAllocator.cpp: implementation of the FixedAllocator class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "FixedAllocator.h"
#include <assert.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

FixedAllocator::FixedAllocator()
{
	numBlocks_ = unsigned char(255);
	allocChunk_ = 0;
	deallocChunk_ = 0;
}

FixedAllocator::~FixedAllocator()
{
	Chunks::iterator i = chunks_.begin();
	for(; i != chunks_.end(); i++)
	{
		i->Release();
	}
	chunks_.clear();
}

void* FixedAllocator::Allocate()
{
	if(allocChunk_ == 0 || allocChunk_->blocksAvailable_ == 0)
	{
		Chunks::iterator i = chunks_.begin();
		for(;;++i)
		{
			if(i == chunks_.end())
			{
				chunks_.push_back(Chunk());
				Chunk& newChunk = chunks_.back();
				newChunk.Init(blockSize_, numBlocks_);
				allocChunk_ = &newChunk;
				allocChunk_->blocksAvailable_ = numBlocks_;
				deallocChunk_ = &chunks_.front();
				break;
			}
			if(i->blocksAvailable_ > 0)
			{
				allocChunk_ = i;
				break;
			}
		}
	}
	assert(allocChunk_ != 0);
	assert(allocChunk_->blocksAvailable_ > 0);

	return allocChunk_->Allocate(blockSize_);
}

void FixedAllocator::Deallocate(void* p)
{
	assert(deallocChunk_ != 0 || allocChunk_ != 0);
	
	size_t size = blockSize_*numBlocks_;
	if(static_cast<size_t>(static_cast<unsigned char*>(p) - deallocChunk_->pData_) < size)
	{
		deallocChunk_->Deallocate(p, blockSize_);
		return;
	}

	Chunks::iterator prev = deallocChunk_;
	Chunks::iterator next = deallocChunk_;

	while(true)
	{
		if(prev != chunks_.begin())
		{
			prev--;
			if(static_cast<size_t>(static_cast<unsigned char*>(p) - prev->pData_) < size)
			{
				deallocChunk_ = prev;
				deallocChunk_->Deallocate(p, blockSize_);
				if(deallocChunk_->blocksAvailable_ == numBlocks_)
				{
					SetToEnd(deallocChunk_);
				}
				return;
			}
		}
		if(next != chunks_.end())
		{
			next++;
			if(static_cast<size_t>(static_cast<unsigned char*>(p) - next->pData_) < size)
			{
				deallocChunk_ = next;
				deallocChunk_->Deallocate(p, blockSize_);
				if(deallocChunk_->blocksAvailable_ == numBlocks_)
				{
					SetToEnd(deallocChunk_);
				}
				return;
			}
		}
		assert(prev != chunks_.begin() || next != chunks_.end());
	}
}

void FixedAllocator::SetToEnd(Chunks::iterator it)
{
	assert(it->blocksAvailable_ == numBlocks_);

	Chunks::iterator itEnd = &chunks_.back();
	if(it != chunks_.end())
	{
		if(itEnd->blocksAvailable_ == numBlocks_)
		{
			itEnd->Release();
			chunks_.pop_back();
			itEnd = &chunks_.back();
		}
		Chunk chunk;
		chunk = *itEnd;
		*itEnd = *it;
		*it = chunk;
		deallocChunk_ = itEnd;
		allocChunk_ = itEnd;
	}
}
